//
// Created by 麻再挺 on 2022/1/12.
//

#include "heap_sort.h"

void adjustHeap(int i, int *a, int count) {
    // 条件判断是否到了叶子结点
    while (i <= count / 2 - 1) {
        // 总数为偶数，最后一个父节点没有右孩子
        int tmp = 2 * i + 2 >= count ? 0 : a[2 * i + 2];
        // max值：左右孩子中更大的那个孩子节点的下标
        int max = a[2 * i + 1] >= tmp ? 2 * i + 1 : 2 * i + 2;
        if (a[max] > a[i]) {
            tmp = a[max];
            a[max] = a[i];
            a[i] = tmp;
            i = max;
        } else break;
    }
}

void heap_sort(int a[], int len) {
    // 停留在构造成功的根堆的前一步
    for (int i = len / 2 - 1; i > 0; i--) {
        adjustHeap(i, a, len);
    }
    while (len > 1) {
        // 构造大根堆
        adjustHeap(0, a, len);
        int tmp = a[0];
        // 交换
        a[0] = a[len - 1];
        a[len - 1] = tmp;
        // 末尾往前移动
        --len;
    }
}
